package com.icbc.DataStructuresAndAlgorithms;

import java.util.HashSet;
import java.util.Stack;

/**
 * 单向链表测试
 */
public class LinkedDomo {
	public static void main(String[] args) {
		//SingleLinkedList queue = new SingleLinkedList();
		//DoubleLinkedList queue = new DoubleLinkedList();
		/*queue.add(1,"宋江" , "窝囊废");
		queue.add(5,"吴用" , "真没用");
		queue.add(3,"林冲" , "青青大草原");
		queue.add(4,"喜洋洋" , "一身毛");
		queue.add(2,"灰太狼" , "平底锅");*/
		//queue.list();
		CircleSingleLinkedList queue = new CircleSingleLinkedList();
		//queue.add(1);
		//queue.list();
		queue.yue1(25, 2);
		System.out.println();
		queue.list();
		System.out.println();
		queue.yue2(25, 2);
		System.out.println();
		queue.list();
		
	}
}

//单向链表
class SingleLinkedList{
	//初始化链表
	LinkedNode head = new LinkedNode(0,"","");
	
	//添加
	public void add(int no,String name,String sex){
		//创建节点
		LinkedNode node = new LinkedNode(no,name,sex);
		//保持头节点不动
		LinkedNode temp = head;
		//循环判断指向的下一个节点不为null,就是有下一个节点
		while (temp.next != null){
			//判断节点的no值大于需要插入的值
			if (temp.next.no > no){
				//将新创建的节点插到此节点之前
				//首先将新节点的next指针指向大于的节点
				node.next = temp.next;
				//再将原来的上个节点指向新的节点
				temp.next = node;
				//直接return不再执行下面
				return;
			}
			//步长,让指针指向下一个
			temp = temp.next;
		}
		//若上面的循环没有执行return,表示此节点需要插入到链表的最后面
		temp.next = node;
	}
	
	//从尾到头打印单链表
	public void listDescPrint(){
		//定义辅助节点
		LinkedNode temp = head;
		//创建一个栈
		Stack<LinkedNode> s = new Stack<>();
		//将链表中的数据取出放入栈中
		while (temp.next != null){
			s.add(temp.next);
			temp = temp.next;
		}
		//将数据从栈中弹出并打印
		while (s.size() > 0){
			System.out.println(s.pop());
		}
	}
	
	//遍历链表
	public void list(){
		LinkedNode te = head;
		while (te.next != null){
			System.out.println(te.next);
			te = te.next;
		}
	}
	
	//反转链表:方式一
	/*思路:将每个节点的next指针都反过来指向它上一个节点,最后再让head的next指向最后一个节点*/
	public void listOrderDesc1(){
		LinkedNode te = head.next;
		LinkedNode te1 = null;
		LinkedNode n;
		while (te != null){
			n = te.next;
			te.next = te1;
			te1 = te;
			te = n;
		}
		head.next = te1;
	}
	
	//反转链表:方式二
	/*思路:创建一个新的头,遍历原来的链表,每取出一个节点都插在新
	链表头的后面其他节点的前面,最后让head的next指向新链表头的next*/
	public void listOrderDesc2(){
		LinkedNode tem = head.next;
		LinkedNode newhead = new LinkedNode(0,"","");
		LinkedNode nn;
		while (tem != null){
			nn = tem.next;
			tem.next = newhead.next;
			newhead.next = tem;
			tem = nn;
		}
		head.next = newhead.next;
	}
	
	
	//定义子节点
	class LinkedNode{
		private int no;
		private String name;
		private String sex;
		private LinkedNode next;
		
		private LinkedNode (int no,String name,String sex){
			this.no = no;
			this.name = name;
			this.sex = sex;
		}
		
		@Override
		public String toString() {
			return "LinkedNode{" +
					"no=" + no +
					", name='" + name + '\'' +
					", sex='" + sex + '\'' +
					'}';
		}
	}
}

//双向链表
class DoubleLinkedList{
	//初始化链表
	LinkedNode head = new LinkedNode(0,"","");
	//添加的标识
	LinkedNode tem = head;
	
	//添加(有序)
	public void addByOrder(int no,String name,String sex){
		//创建节点
		LinkedNode node = new LinkedNode(no,name,sex);
		//保持头节点不动
		LinkedNode temp = head;
		//循环判断指向的下一个节点不为null,就是有下一个节点
		while (temp.next != null){
			//判断节点的no值大于需要插入的值
			if (temp.next.no > no){
				//将新创建的节点插到此节点之前
				//首先将新节点的next指针指向大于的节点
				node.next = temp.next;
				temp.next.prev = node;
				//再将原来的上个节点指向新的节点
				temp.next = node;
				node.prev = temp;
				//直接return不再执行下面
				return;
			}
			//步长,让指针指向下一个
			temp = temp.next;
		}
		//若上面的循环没有执行return,表示此节点需要插入到链表的最后面
		temp.next = node;
		node.prev = temp;
	}
	
	//添加(无序)
	public void add(int no,String name,String sex){
		//创建节点
		LinkedNode node = new LinkedNode(no,name,sex);
		node.prev = tem;
		tem.next = node;
		tem = node;
	}
	
	//从尾到头打印单链表
	public void listDescPrint(){
		//定义辅助节点
		LinkedNode temp = head;
		//创建一个栈
		Stack<LinkedNode> s = new Stack<>();
		//将链表中的数据取出放入栈中
		while (temp.next != null){
			s.add(temp.next);
			temp = temp.next;
		}
		//将数据从栈中弹出并打印
		while (s.size() > 0){
			System.out.println(s.pop());
		}
	}
	
	//遍历链表
	public void list(){
		LinkedNode te = head;
		while (te.next != null){
			System.out.println(te.next);
			te = te.next;
		}
	}
	
	//定义子节点
	class LinkedNode{
		private int no;
		private String name;
		private String sex;
		private LinkedNode next; //指向下一个节点
		private LinkedNode prev; //指向上一个节点
		
		private LinkedNode (int no,String name,String sex){
			this.no = no;
			this.name = name;
			this.sex = sex;
		}
		
		@Override
		public String toString() {
			return "LinkedNode{" +
					"no=" + no +
					", name='" + name + '\'' +
					", sex='" + sex + '\'' +
					'}';
		}
	}
}

//单向环形链表
class CircleSingleLinkedList{
	//定一个类似头节点的节点,数据随便
	LinkedNode first = null;
	
	
	//添加,传入参数是表示创建多少个节点
	public void add(int num){
		if (num < 1){
			System.out.println("参数异常,参数不应小于1!");
		}
		
		//定一个遍历的指针节点
		LinkedNode cur = null;
		for (int a = 1 ; a <= num ; a ++){
			LinkedNode node = new LinkedNode(a);
			if (a == 1){
				first = node;
				first.next = first;
				cur = first;
			}else{
				cur.next = node;
				node.next = first;
				cur = node;
			}
		}
	}
	
	//遍历链表
	public int list(){
		//定一个遍历的指针节点
		int size = 0;
		if (first == null){
			System.out.println("未初始化链表!");
			return size;
		}
		LinkedNode cur = first;
		do {
			System.out.println(cur);
			cur = cur.next;
			size ++;
		}while(cur != first);
		return size;
	}
	
	//约瑟夫问题(非删除节点,使用逻辑跳过删除点)
	public void yue1(int num,int n){
		//创建指定的节点数量,num同样也是链表的长度
		add(num);
		//定义一个标识,用于遍历
		LinkedNode cur = first;
		//使用set集合存储以出列的编号
		HashSet<Integer> set = new HashSet<>();
		//使用死循环来遍历链表
		for(int a = 1 ; ; a ++){
			//首先判断此编号是否已经出列
			//出列的话就将指针后移并且将a进行复位,用于下面取余准确
			if (set.contains(cur.no)) {
				cur = cur.next;
				a--;
				if (set.size() >= num) break;
			}else {
				//未出列,就对该数据判断是否满足出列要求,满足则将数据保存到出列的集合中,并且将指针后移
				if (a % n == 0){
					set.add(cur.no);
					System.out.print(cur.no + " ");
				}
				cur = cur.next;
			}
		}
	}
	
	//约瑟夫问题(删除节点方式)
	public void yue2(int num,int n){
		//创建指定的节点数量,num同样也是链表的长度
		add(num);
		//定义一个标识,此标识指向待删除节点的前一个节点,
		//初始化指针first的前一个节点,因为单向链表节点本身无法删除自身
		LinkedNode before = first;
		//找到链表的最后一个节点,赋给before
		while (before.next != first) {
			before = before.next;
		}
		
		//遍历链表进行删除
		for (int a = 1 ; ; a ++){
			if (a % n == 0){
				System.out.print(first.no + " ");
				before.next = first.next;
				if (before == first) break;
			}
			before = first;
			first = first.next;
		}
	}
	
	//定义链表子节点
	class LinkedNode{
		private int no;
		private LinkedNode next; //指向下一个节点
		
		private LinkedNode (int no){
			this.no = no;
		}
		
		@Override
		public String toString() {
			return "LinkedNode{" +
					"no=" + no +
					'}';
		}
	}
}
